#include <vector>
#include <stack>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        // 迭代方法:  步骤: 1. 一直访问左子节点并入栈 2. 弹出栈顶节点并访问 3. 访问右子节点
        vector<int> res;
        stack<TreeNode *> st;
        TreeNode *cur = root;
        while (cur || !st.empty()) // 注意这里的条件: cur不为空或者栈不为空
        {
            while (cur) // 一直访问左子节点并入栈
            {
                st.push(cur);
                cur = cur->left;
            }
            // 左子节点访问完后，弹出栈顶节点并访问
            cur = st.top(); // 获取栈顶节点
            st.pop();
            res.push_back(cur->val); // 访问节点
            cur = cur->right;        // 访问右子节点
        }
        return res;
    }
    // 递归方法：步骤: 1. 访问左子树 2. 访问根节点 3. 访问右子树
    void inorder(TreeNode *root, vector<int> &res)
    {
        if (!root)
            return;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
};